Many of the most exciting applications of computing today are in robotics. Recent advances in robotics have greatly expanded the opportunities for robots to change the way people live. Robots are being developed for a wide spectrum of real-world applications including health care, personal assistance, general-purpose manufacturing, search-and-rescue, and military operations. Unlike traditional robotics applications in which a robot operates in a tightly controlled environment (e.g., on an assembly line where the environment is static and known a priori), these applications require the robot to perform motion planning.
Motion planning is the process of determining how a robot should move to achieve a goal. For example, a robot may wish to move its arm to reach a desired object without colliding with itself or any other object. The ability to perform motion planning to navigate and manipulate objects is critical to dealing with natural environments that are not heavily controlled or engineered. The robot first perceives information about the physical world around it, and then the computer determines how to control the physical robot so that the robot can navigate in this perceived environment.
In many situations, a major constraint on the usefulness of robots is their ability to perform real-time motion planning in environments with obstacles. Motion planning algorithms tend to be computationally intensive, requiring a vast number of collision checks for each movement. Existing techniques for collision detection are generally implemented in software running on one or more general-purpose processors and/or graphics processing units (GPUs). However, running collision detection software on general-purpose processors is insufficiently fast for real-time motion planning and/or is too power-hungry (if using GPUs) for many target applications.